package tree;

import java.util.HashMap;
import java.util.Map;

/**题目：根据二叉树的中序和后续构建二叉树
 * @Author Gavin
 * @date 2022.01.04 22:35
 */
public class tree_14 {

    public TreeNode buildTree(int[] post,int postStart,int postEnd,
                              int inStart,Map<Integer,Integer> inPos){
        if(postStart>postEnd)return null;
        TreeNode root=new TreeNode(post[postEnd]);
        int rootIdx=inPos.get(post[postEnd]);
        int leftLen=rootIdx-inStart;//获取到左子节点的个数
        /**
         * postStart+leftLen 的大小是包括了根节点的，所以这里需要-1
         */
        root.left=buildTree(post,postStart,postStart+leftLen-1,inStart,inPos);
        root.right=buildTree(post,postStart+leftLen,postEnd-1,rootIdx+1,inPos);
        return root;
    }

    public TreeNode solution(int[] in,int[]post){
        Map<Integer,Integer> inPos=new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inPos.put(in[i],i);
        }
        return buildTree(post,0,post.length-1,0,inPos);
    }
}
